1. Field of the Invention
The present invention relates to a method and apparatus for printing an image in which a printing operation can be changed before the printing operation commences in accordance with predictions as to how much of the printer""s resources will be used in printing the image. The image is stored in a coded representation before being converted into a full raster image, the coded representation being susceptible to accurate modeling of resources used in converting to a full raster image. Accordingly, the usage of printer resources in converting the coded representation of the image into a full raster image can be predicted accurately and it can be determined before printing whether the printer has sufficient resources to print the image. In the event that the prediction indicates that there are insufficient resources, resources can be re-allocated so as to permit the image to be printed.
2. Description of the Related Art
Recently, printing apparatus such as laser beam printers which form images by selectively printing pixels on a page have become exceedingly popular because of their flexibility, printing speed and low cost. Such printing apparatuses print images by scanning across a page while selectively printing individual pixels on the scan line. The page is advanced (in printers like laser beam printers the page is advanced continuously while printing) and additional scan lines are formed. The collection of printed pixels from all the scan lines on the page forms the desired image.
Whether pixels are printed on the page, and where those pixels are printed during a scanning operation, are determined by a printer controller which operates in accordance with a stored raster image of the print image. A raster is a computer representation of each of the pixels in the print image, and is stored in bit map memory in the controller. In a bit map memory, there is a one-for-one correspondence between pixels on a printed page and memory locations in the bit map memory.
All printing apparatuses must operate within the constraints of the available resources. For example, the controller, which is typically a microprocessor forming a central processing unit (xe2x80x9cCPUxe2x80x9d), has only a limited amount of processing power and is able to manipulate only a limited amount of data including image data within any one time period. The controller has access to only a limited amount of memory including the bit map memory. Some printers are provided with other resources such as external memory devices which are accessible through a communication line which has only a limited amount of bandwidth (or data-carrying speed).
Conventional printing apparatuses use the finite amount of resources that are available to them only inefficiently. For example, FIG. 1 is an illustration of a typical CPU resource usage pattern in a printer. As shown in FIG. 1, CPU usage varies widely between peak CPU usage and relatively low CPU usage. Peak CPU usage occurs between printed pages during creation of the raster image in bit map memory while low CPU usage occurs as a page is being printed.
The reason for this inefficiency is that, to ensure that the image is printed properly, printing apparatuses such as laser beam printers which form pixels by scanning must have a full raster image of the print image developed in bit map memory before printing can commence. This is because scanning printing apparatuses print at a uniform rate while a page is being printed. That is, once page printing has begun, printing continues at a uniform rate until page printing ends. Accordingly, to assure that the print engine does not run out of data to print (a condition known as data underflow), the entire image to be printed is developed into a raster image in bit map memory before printing commences. The CPU is responsible for developing the raster image into bit map memory, and this process represents peak CPU usage. During actual printing of the image, however, the CPU needs only to monitor the bit map memory to ensure that the raster image is provided to the print engine at the same rate as the print engine prints it. This relatively simple task represents low CPU usage.
Correspondingly, and as further shown in FIG. 1, when CPU usage is at its maximum, memory usage is at its minimum. This is because bit map memory is full only at a period just prior to image printing. As described above, this corresponds to a period when CPU functions are minimal.
For the simplest print systems, such inefficiencies are tolerable. For example, to print a simple black and white image at low resolution such as 300 dots per inch (dpi) on a standard 8xc2xdxc3x9711 inch sheet of paper requires approximately 1 megabyte (Mb) of bit map memory. The price of 1 Mb of memory is low enough so that it is acceptable for large portions of the memory to be unused for long periods of time. This remains so even if the bit map memory is double buffered, that is, 2 Mb of memory are provided. Double buffering is desirable because it allows the CPU to develop a succeeding page of image data into a raster image in one buffer at the same time that the CPU is printing a current page of image data from the other buffer. Double buffering helps to provide a continuous stream of raster image data to the print engine thereby obtaining better inter-page throughput in a relatively cost effective manner.
But, as resolution increases, and as greater capabilities (for example, halftone and color) are desired, such inefficiencies can no longer be tolerated. For example, at 600 dpi resolution, four times as much memory is needed than is needed at 300 dpi to store a full raster image. The effect becomes even more pronounced when halftone or color images are considered. For example, to provide sixteen grey levels for each pixel in a halftone image requires 4 bits per pixel. Multiplying four bits per pixel by 4 Mb to store a 600 dpi raster image results in a requirement for a 16 Mb memory to store a halftone raster image. When color is considered, the memory requirements become even greater. For example, to encode four colors per pixel with 8 bits for each color means that 32 bits are required for each pixel. Multiplying 32 bits by 4 Mb for a 600 dpi raster image results in a 128 Mb memory requirement to store a full color 600 dpi raster image. The price for such large amounts of memory is not acceptable for wide commercial acceptance, and becomes even worse when double buffering is provided to reduce inter-page delay.
It has been considered to increase the apparent size of physical memory through the use of virtual memory in which off-line memory devices such as a disk drive are used to provide additional memory space and which are connected to a printer controller through a communication link. The use of virtual memory in a printing apparatus has not proved entirely satisfactory. This is because of the uncertainty involved in ensuring that there is sufficient bandwidth in the communication link so as to provide timely pixel data to the printer engine and avoid data underflow.
It is an object of the present invention to use resources in a printer more efficiently so as to provide a printer having greater capability without the need of increasing the amount of physical resources available to it.
In one aspect, the invention is a printing apparatus in which an image is stored in a coded, compact representation before it is rendered into a full rasterized image. The representation is such that the resources that are needed to render a full rasterized image can be predicted with great accuracy. Predictor functions are provided to predict resource usage so as to determine, prior to printing, whether the printer has sufficient resources to conduct printing. If sufficient resources are available, then printing is performed. If the resources are not available, trade-offs between resources can be made so as to allow printing to take place.
Because the coded representation allows dynamic and adaptive use of printer resources, the representation is referred hereafter as the dynamic adaptive resource (or resolution) technology, or xe2x80x9cDARTxe2x80x9d, representation.
Consider, for example, the resources depicted graphically in FIG. 2, namely, CPU power, memory, and bandwidth. CPU power refers to the speed and ability with which a CPU in a printer controller can manipulate data and process it from one form to another. Memory refers to the amount of memory available to the printer. Bandwidth refers to the bandwidth or data-carrying speed of a communication link to an external memory device. Included in bandwidth are any known delays of the external memory device, for example, access time, disk head delays, and disk rotation speed.
Any one printer will have an envelope of resources available to it defined by a point representing the maximum CPU power, the maximum memory, and the maximum bandwidth. If predictor functions predict that rendering the DART representation into a full raster image will exceed one of these resources, then resource trade-off can be conducted. For example, if it is determined that there is insufficient memory to store the image, but that CPU power is underutilized (represented by point A in FIG. 2), then it is possible to substitute a different DART representation, one which uses less memory but which requires more CPU power to render the representation into a full raster image. Thus, memory has been exchanged for CPU power. This trade-off shifts point A to point Axe2x80x2 which is within the resource envelope available to the printer and allows printing to commence.
It is also possible to degrade the image such as by lowering the print resolution or by limiting the number of grey levels for halftone images or colors for color images. Degrading the image eases memory requirements without putting a further burden on the CPU. This trade-off results in a shift of point A to point Axe2x80x3 which is within the printer resource envelope and which allows printing to commence.
Conversely, the predictor functions may predict that the CPU has insufficient CPU power to render a full raster image from the DART representation in sufficient time to provide the raster image to the print engine, that is, there would be data underflow. If there is sufficient memory available (represented by point B in FIG. 2), then CPU power may be exchanged for memory space, e.g. by pre-rasterizing the portion of the image that requires too much CPU power. This trade-off shifts point B to point Bxe2x80x2 which is within the resource envelope of the printing apparatus so that printing may commence.
Likewise, it is also possible to trade-off CPU power and/or memory with bandwidth. For example, in a case like point C in which it is predicted that maximum CPU power is already being expended to render a full raster image from the DART representation, but that memory resources are still exceeded, then it is possible to trade-off memory for bandwidth, e.g. by causing a portion of the image to be stored off-line and retrieved when needed through a communication link. This shifts point C to point Cxe2x80x2 which is within the resource envelope of the printing apparatus. The predictor functions ensure that the bandwidth is sufficient so that raster image data is timely provided to the print engine and the print engine does not suffer from data underflow.
This brief summary has been provided so that the nature of the invention may be understood quickly. A fuller understanding of the invention may be obtained by reference to the following detailed description in conjunction with the remaining drawings in which: